home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / plane / _convex_hull.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  1.4 KB  |  85 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _convex_hull.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #include <LEDA/convex_hull.h>
  17. #include <LEDA/plane.h>
  18.  
  19. list<point> CONVEX_HULL(list<point> L)
  20. { 
  21.   if (L.length() < 3) return L;
  22.  
  23.   list<point> CH;
  24.   list_item last;
  25.   point p;
  26.  
  27.   L.sort();  // sort points lexicographically
  28.  
  29.  
  30.   // initialize convex hull with first two points
  31.  
  32.   p = L.pop();
  33.   CH.append(p);
  34.   while (L.head() == p) L.pop();
  35.   last = CH.append(L.pop());
  36.  
  37.  
  38.   // scan remaining points
  39.  
  40.   forall(p,L)
  41.   {
  42.     if (p == CH[last]) continue;  // multiple point
  43.  
  44.     // compute upper tangent (p,up)
  45.  
  46.     list_item up = last;
  47.     list_item it = CH.cyclic_succ(up);
  48.  
  49.     while (left_turn(CH[it],CH[up],p))
  50.     { up = it;
  51.       it = CH.cyclic_succ(up);
  52.      }
  53.  
  54.  
  55.     // compute lower tangent (p,low)
  56.  
  57.     list_item low = last;
  58.     it = CH.cyclic_pred(low);
  59.  
  60.     while (right_turn(CH[it],CH[low],p))
  61.     { low = it;
  62.       it = CH.cyclic_pred(low);
  63.      }
  64.  
  65.  
  66.     // remove all points between up and low
  67.  
  68.     if (up != low)
  69.     { it = CH.cyclic_succ(low);
  70.  
  71.       while (it != up)
  72.       { CH.del(it);
  73.         it = CH.cyclic_succ(low);
  74.        }
  75.      }
  76.  
  77.     // insert new point
  78.  
  79.     last = CH.insert(p,low);
  80.  
  81.    }
  82.  
  83.   return CH;
  84. }
  85.